package ch2.part3;

/**
 * 栈的数据结构 - 数组实现
 * 时间复杂度：
 * - 入栈：O(n)=1
 * - 出栈：O(n)=1
 *
 * @author liuwanxiang
 * @version 2019/05/14
 */
public class MyArrayStack {

    private Integer[] array;
    private int pointer;

    public MyArrayStack(int capacity) {
        this.array = new Integer[capacity];
        this.pointer = -1;
    }

    /**
     * 入栈
     * 时间复杂度：O(n)=1
     *
     * @param data
     */
    public void push(Integer data) {
        if (pointer >= array.length - 1) {
            throw new RuntimeException("栈溢出~");
        }
        array[++pointer] = data;
    }

    /**
     * 出栈
     * 时间复杂度：O(n)=1
     *
     * @return
     */
    public Integer pop() {
        if (pointer < 0) {
            throw new RuntimeException("栈已空~");
        }
        Integer rst = array[pointer];
        array[pointer] = null;
        pointer--;
        return rst;
    }

    public static void main(String[] args) {

        MyArrayStack stack = new MyArrayStack(3);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }

}
